package com.qisi.kandroidshalon.leetcode.heap;

import android.util.Log;

import com.qisi.kandroidshalon.leetcode.Util;

import java.util.Map;

public class BigHeap {

    public static void heapSort(Integer[] arr) {
        buildBigHeap(arr);
        int heapSize = arr.length;
        while (heapSize > 0) {
            Util.swap(arr, 0, heapSize - 1);
            heapSize--;
            heapInsertDown(arr, 0, heapSize);
        }
    }

    public static void buildBigHeap(Integer[] arr) {
        int heapSize = 0;
        while (heapSize < arr.length) {
            insert2Heap(arr, heapSize++);
        }
    }

    /**
     * 执行一次大顶堆插入
     * i
     * 2i+1 2i+2
     *
     * @param arr
     * @param heapSize
     * @return
     */
    private static int insert2Heap(Integer[] arr, int heapSize) {
        //从堆的下一个元素开始
        int scanIndex = heapSize;
        while (scanIndex > 0) {
            int pIndex = (scanIndex - 1) / 2;
            if (arr[scanIndex] <= arr[pIndex]) {
                break;
            }
            Util.swap(arr, pIndex, scanIndex);
            scanIndex = pIndex;
        }

        return heapSize + 1;
    }

    public static void rmAndRebuildHeap(Integer[] arr) {
        int heapSize = arr.length;
        int scanIndex;
        while (heapSize > 0) {
            Util.swap(arr, heapSize - 1, 0);//大顶堆顶部交换到最后，size--
            heapSize--;

            scanIndex = 0;
            while (scanIndex < heapSize) {
                int childLeft = 2 * scanIndex + 1;
                int childRight = 2 * scanIndex + 2;

                //没有子节点了，结束下沉
                if (childLeft > heapSize - 1) {
                    break;
                }
                int maxChild = childLeft;
                if (childRight <= heapSize - 1) {//俩孩子都有
                    maxChild = arr[childLeft] > arr[childRight] ? childLeft : childRight;
                }

                //和如果比孩子大就终止
                if (arr[scanIndex] >= arr[maxChild]) {
                    Log.i("LeetCodeUtil", "下沉终止=======");
                    break;
                }
                Util.swap(arr, scanIndex, maxChild);
                //索引向下沉
                scanIndex = maxChild;
                Log.i("LeetCodeUtil", "=======");
                Util.dumpArray(arr);
            }
        }
    }

    /**
     * arr[index]的数尝试往下沉，重构大根堆
     *
     * @param arr
     * @param index    要调整的索引
     * @param heapSize 大根堆范围
     */
    public static void heapInsertDown(Integer[] arr, int index, int heapSize) {
        int leftChild = 2 * index + 1;
        while (leftChild < heapSize) {//没有超过大根堆范围
            int maxChild = leftChild;
            int rightChild = leftChild + 1;
            if (rightChild < heapSize) {
                maxChild = arr[leftChild] > arr[rightChild] ? leftChild : rightChild;
            }

            //如果当前比孩子大，则终止下沉
            if (arr[index] >= arr[maxChild]) {
                Log.i("LeetCodeUtil", "下沉终止=======");
                break;
            }
            //比孩子小，则继续往下沉
            Util.swap(arr, maxChild, index);
            leftChild = maxChild;
        }
    }
}
